﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class MagicStrings
    {
        public MagicStrings()
        {
            int testCase = Int32.Parse(Console.ReadLine());
            while (testCase-- > 0)
            {
                int resultWordLength = 0;
                string inputString = Console.ReadLine().Trim();
                char[] inputList = inputString.ToCharArray();
                int[,] dataBoard = new int[inputString.Length, inputString.Length];
                int[,] resultBoard = new int[inputString.Length + 2, 2];
                
                resultBoard[0, 0] = -1;
                resultBoard[0, 1] = -1;
                //입력
                for (int i = 0; i < inputString.Length; i++)
                {
                    for (int j = 0; j < inputString.Length; j++)
                    {
                        if(inputList[i] > inputList[inputString.Length - 1 - j])
                        {
                            dataBoard[i, j] = 1;
                        }
                        else if (inputList[i] < inputList[inputString.Length - 1 - j])
                        {
                            dataBoard[i, j] = -1;
                        }
                        else
                        {
                            dataBoard[i, j] = 0;
                        }
                    }
                }
                int x = 0, y = 0;
                int maxX = inputList.Length - 1;
                int maxY = inputList.Length - 1;
                int odd = -1;
                //처리
                for (int i = 0; i < inputString.Length; i++)
                {
                    resultWordLength = i;
                    FindValue(ref x, ref y, odd, dataBoard, x, y, maxX, maxY);
                    
                    if (x < 0 && y < 0)
                    {
                        x = maxX;
                        y = maxY;
                        resultBoard[i + 1, 0] = x;
                        resultBoard[i + 1, 1] = y;
                        resultBoard[i + 2, 0] = inputList.Length - 1;
                        resultBoard[i + 2, 1] = inputList.Length - 1;
                        break;
                    }
                    resultBoard[i + 1, 0] = x;
                    resultBoard[i + 1, 1] = y;
                    x++;
                    y++;
                    maxX = inputList.Length - y - 1;
                    maxY = inputList.Length - x - 1;
 
                    odd *= -1;

                    if (x > maxX || y > maxY)
                    {
                        resultBoard[i + 2, 0] = inputList.Length - 1;
                        resultBoard[i + 2, 1] = inputList.Length - 1;
                        break;
                    }
                }
                resultWordLength++;
                //알파뱃 순서로...
                odd = -1;
                for (int i = 1; i <= resultWordLength; i++)
                {
                    int minX = resultBoard[i - 1, 0] + 1;
                    int minY = resultBoard[i - 1, 1] + 1;
                    maxX = resultBoard[i + 1, 0] - 1;
                    maxY = resultBoard[i + 1, 1] - 1;
                    FindFirstValue(out x, out y, odd, dataBoard, minX, minY, maxX, maxY, inputList);
                    resultBoard[resultWordLength + 1, 0] = inputList.Length - x - 1; ;
                    resultBoard[resultWordLength + 1, 1] = inputList.Length - y - 1; ;
                    resultBoard[i, 0] = x;
                    resultBoard[i, 1] = y;
                    odd *= -1;
                }
                //출력
                StringBuilder output = new StringBuilder();
                for (int i = resultWordLength; i > 0; i--)
                {
                    output.Insert(0, inputList[resultBoard[i, 0]]);
                    output.Append(inputList[inputList.Length - resultBoard[i, 1] - 1]);
                }
                Console.WriteLine(output);
            }
        }
        private void FindFirstValue(out int x, out int y,int value, int[,] dataBoard, int minX, int minY, int maxX, int maxY, char[] inputList)
        {
            x = 0; y = 0;
            int minValue = int.MaxValue;
            int justMinValue = int.MaxValue;
            int justX = 0;
            int justY = 0;
            for (int x2 = minX; x2 <= maxX; x2++)
            {
                for (int y2 = minY; y2 <= maxY; y2++)
                {
                    if (dataBoard[x2, y2] == value && inputList[x2] < minValue && x2 >= y2)
                    {
                        minValue = inputList[x2];
                        x = x2;
                        y = y2;
                    }
                    if (inputList[x2] < justMinValue && x2 >= y2)
                    {
                        justMinValue = inputList[x2];
                        justX = x2;
                        justY = y2;
                    }
                }
            }
            if (x == 0 && y == 0)
            {
                x = justX;
                y = justY;
            }
        }
        private void FindValue(ref int x, ref int y, int value, int[,] dataBoard, int minX, int minY, int maxX, int maxY)
        {
            bool findIt = false;
            if (x <= maxX && y <= maxY && dataBoard[x, y] == value)
            {
                findIt = true;
            }
            else if (x == y)
            {
                x = minY;
                y++;
            }
            else if (y > x)
            {
                int temp = x;
                x = y;
                y = temp;
            }
            else if (y < x)
            {
                int temp = x;
                x = y;
                y = temp;
                x++;
            }
            if (x > maxX && y > maxY)
            {
                x = -1;
                y = -1;
                return;
            }
            else if(!findIt)
            {
                FindValue(ref x, ref y, value, dataBoard, minX, minY, maxX, maxY);
            }
            return;
        }
    }

}
